package org.basic.algorithm.medium;

import java.util.HashSet;
import java.util.Set;

/**
 * 无重复字符的最长子串
 * <p>
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 * <p>
 * 示例 1:
 * 输入: s = "abcaabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * <p>
 * 示例 2:
 * 输入: s = "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * <p>
 * 示例 3:
 * 输入: s = "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 * 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 * <p>
 * 示例 4:
 * 输入: s = ""
 * 输出: 0
 * <p>
 * 提示：
 * 0 <= s.length <= 5 * 104
 * s 由英文字母、数字、符号和空格组成
 *
 * @author LiKun
 * @date 2021/10/9 10:34
 */
public class LongestSubstringWithoutRepeatingCharacters {
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("pwwkew"));
    }

    /**
     * 利用char类型与int类型转换 && 数组 实现
     */
    public static int lengthOfLongestSubstring(String s) {
        int left = 0, length = 0;
        int[] lastNext = new int[128];

        for (int i = 0; i < s.length(); i++) {
            // 当前最大无重复子串的左边界索引(跳过后缀重复字符)
            left = Math.max(left, lastNext[s.charAt(i)]);
            length = Math.max(length, i - left + 1);
            // 当前子串该字符的最右边界
            lastNext[s.charAt(i)] = i + 1;
        }

        return length;
    }

    /**
     * 优化策略：跳过重复的字母(最大公共子串)
     *
     * @param s 给定字符串
     *
     * @return 无重复字符的最长子串长度
     */
    @Deprecated
    public static int lengthOfLongestSubstringOpt(String s) {
        boolean isClear = true;
        int length = 0, index = 0;
        Set<Character> hashSet = new HashSet<>(s.length());

        // i：起始比较字符
        for (int i = 0; i < s.length(); i++) {
            if (isClear) {
                hashSet.clear();
                isClear = false;
                index = i != 0 ? --i : 0;
            } else {
                hashSet.remove(s.charAt(i - 1));
            }

            // 寻找自起始字符开始的最大无重复子串长度
            while (index <= s.length() - 1 && !hashSet.contains(s.charAt(index))) {
                hashSet.add(s.charAt(index++));
            }

            // 最大无重复子串长度
            length = Math.max(length, index - i);

            // 优化后缀字符重复情况
            while (index < s.length() - 1 && s.charAt(index - 1) == s.charAt(index)) {
                isClear = true;
                i = index++;
            }
        }

        return length;
    }
}
